1. Field of the Invention
The invention relates to apparatus for converting numbers bidirectionally between binary and another base, such as binary-coded decimal.
2. Description of Related Art
A number coded according to an arbitrary radix b may be stored in a data processing system as a sequence of nibbles (distinct groups of bits), each nibble containing one radix-b digit. In the common example of BCD, each nibble is four bits wide and contains a decimal digit ranging in value between zero and nine.
It is often necessary to convert numbers between binary and radix b, and numerous algorithms using standard hardware have been developed to accomplish this. A typical algorithm for converting a radix-b number to binary operates by first initializing a binary accumulator to zero and then going into a loop in which the leading digit is peeled off the radix-b number and added into the binary accumulator while the previous contents of the accumulator are concurrently multiplied by b. One problem with using this algorithm is that multiplication is usually a two-step process, requiring two cycles to complete. The sum and carrying bits from a carry/save adder (CSA) are generated on the first cycle, and they are added together (and with the leading radix-b digit) on the second cycle. The approach therefore requires two clock cycles for each radix-b digit to complete.
The conversion may be improved to perform in one clock cycle per radix-b digit if two multiply-and-add algorithms are interleaved in the same multiplier. For example, a first accumulation may be made by multiplying the first digit by b.sup.2 and adding the third digit, then multiplying the result by b.sup.2 and adding the fifth digit, etc. The second accumulation may be obtained by multiplying the second digit by b.sup.2 and adding the fourth digit, multiplying the result by b.sup.2 and adding the sixth digit, etc. While one accumulation is in the multiply stage, the other accumulation is in the adding stage. After both accumulations are complete, the appropriate one is multiplied by b and added to the other to obtain the binary result. This technique converts one digit to binary for each clock cycle, but as can be seen, adds significant complexity in control logic.
Additionally, multipliers are usually implemented with limited width in order to preserve their speed. For example, whereas one multiplicand may be 32 bits wide, the other may be limited to 8 bits with width. Since the wider multiplicand must be reserved for the previous accumulation, the smaller input must be used for the number b.sup.2. This limits the radix from which the conversion is made to b=15, for an 8-bit wide multiplicand.
Many algorithms have been developed for conversion from binary to radix-b, as well. One such algorithm, which is particularly useful with the present invention, is described in U.S. Pat. No. 3,803,392 to Amdahl and Clements. It involves first multiplying the binary number by a small constant b.sup.-m to create a product having an integer part and a fractional part. If m is chosen to be equal to n-1, where n is the maximum number of radix-b digits which may be obtained from the binary number, then the integer part of the product already contains the high-order digit of the radix-b number. The fractional part is then successively multiplied by b to generate a new radix-b digit in the integer part after every multiplication. As the digits are generated they are shifted into a final result register and the integer part cleared for the next digit.
For conversion of a 32-bit binary number into a 10-digit decimal number, the conversion may be performed in two stages. In the first stage, the initial multiplication is by 10.sup.-4 to obtain a first product. The integer portion of the first product is stored, and the fractional part is used to generate the low-order four digits of the result. Then, only if the integer part is nonzero, the high-order six digits are obtained by multiplying the integer portion of the first product by 10.sup.-5. The high-order six digits are then generated as above. This variation speeds up conversion of binary numbers less than 10,000 at the slight expense of conversion of numbers greater than or equal to 10,000. Like the convert-to-binary algorithm described above, however, both the one-stage version and the two-stage version of this algorithm require the services of a multiplier. Since the result of each multiplication is needed before the next one begins, two clock cycles are required to generate each radix-b digit.
It may be possible to speed the above conversion algorithms by using a highly integrated general purpose combinational multiplier to perform the iterative multiplications. This is usually not an option in a high-speed mainframe computer system, however, in which various technical and business considerations dictate that all logic be implemented in the same technology. Additionally, presently available multipliers may still be too slow to perform in one clock cycle at the clock frequencies used in high-speed mainframe computer systems. The clock frequency may be slowed enough to accommodate the longer delays inherent in such combinational multipliers, such that each multiplication is performed in one clock cycle, but the slower clock frequency would significantly degrade the throughput of the system as a whole even if it does provide a net increase in the speed at which conversions are performed.